use std::collections::BinaryHeap;
use crate::solution::Solution;

impl Solution {
    // 第一种解法:
    // 就是先对数组排序， 再取范围切片求值， 比较简单
    pub fn trim_mean(mut arr: Vec<i32>) -> f64 {
        arr.sort();
        arr[(arr.len() / 20)..(arr.len() - arr.len() / 20)].iter().sum::<i32>() as f64 / (arr.len() as f64 * 0.9)
    }

    pub fn trim_mean1(arr: Vec<i32>) -> f64 {
        let mut a = arr;
        a.sort_unstable();
        let r = a.len() / 20;
        let s:i32 = a[r..a.len()-r].iter().sum();
        s as f64 / (a.len() - r * 2) as f64
    }

    // 第二种解法:
    // 建两个二叉堆，来维护数组两端要排除的数据。 -> 二叉堆？？
    pub fn trim_mean2(arr: Vec<i32>) -> f64 {
        let r = arr.len() / 20;
        let mut heap_min = BinaryHeap::with_capacity(r+1);
        let mut heap_max = BinaryHeap::with_capacity(r+1);
        let mut i = 0;
        // warning: value assigned to `sum` is never read
        // let mut sum = 0;
        while i < 2 * r {
            heap_min.push(arr[i]);
            heap_max.push(-1 * arr[i+1]);
            i += 2;
        }
        // mut 加在这儿就不会警报了!
        let mut sum = Solution::ex_heap(&mut heap_max, &mut heap_min, arr[i as usize]);
        i += 1;
        // for j in 0..(r-1): if this is intentional, prefix it with an underscore: `_j`
        for _j in 0..(r-1) {
            sum = Solution::ex_heap(&mut heap_max, &mut heap_min, sum);
        }
        while i < arr.len() {
            sum += Solution::ex_heap(&mut heap_max, &mut heap_min, arr[i]);
            i += 1;
        }
        sum as f64 / (arr.len() - r * 2) as f64
    }

    fn ex_heap(h_max: &mut BinaryHeap<i32>, h_min: &mut BinaryHeap<i32>, v: i32) -> i32 {
        h_min.push(v);
        h_max.push(-1 * h_min.pop().unwrap());
        h_max.pop().unwrap() * -1
    }

}

// 目录里其他.rs文件有问题，也会影响到其他.rs文件，导致报错
#[cfg(test)]
mod tests {
    // 引用其他目录的impl Solution的话：use crate::algorithm::Solution;
    use super::*;

    #[test]
    fn test_1() {
        let arr : Vec<i32> = vec![1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3];
        let result = Solution::trim_mean(arr);
        println!("{}", result);

        assert_eq!(result, 2.00000);
    }

    #[test]
    fn test_2() {
        let arr : Vec<i32> = vec![1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3];
        let result = Solution::trim_mean1(arr);
        println!("{}", result);

        assert_eq!(result, 2.00000);
    }

    #[test]
    fn test_3() {
        let arr : Vec<i32> = vec![1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3];
        let result = Solution::trim_mean2(arr);
        println!("{}", result);

        assert_eq!(result, 2.00000);
    }


}
